package ljl.codetop;

import commons.StupidQuestion;

import java.util.Arrays;

@StupidQuestion("草！")
public class _41_find_missing_positive {

    /**
     * todo 没 try 出来
     */
    static class tryout {

        // 0,1,2 -1,1,3,4 7,8,9,11,12
        public int firstMissingPositive(int[] nums) {
            Arrays.sort(nums);
            int prev = nums[0];
            for (int num : nums) {
                if (prev + 1 < num && prev + 1 > 0)
                    return prev + 1;
                prev = num;
            }
            return prev + 1 > 0 ? prev + 1 : 1;
        }
    }

    /**
     * 第二次尝试，又错了，错哪了？以为每个数只有一个，找到第一个和下标不一样的就返回，直接就错了
     */
    static class tryout2 {
        public int firstMissingPositive(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; ++i) {
                if (nums[i] <= 0) {
                    nums[i] = n + 1;
                }
            }
            Arrays.sort(nums);
            for (int i = 0; i < n; i++) {
                if (nums[i] != i + 1)
                    return i + 1;
            }
            return n + 1;
        }
    }

    static class off1 {
        public int firstMissingPositive(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; ++i) {
                if (nums[i] <= 0) {
                    nums[i] = n + 1;
                }
            }
            // 这个循环非常难
            // 现在如果遇到负数，一定是正数过来的。
            // -3 -> 3 -> nums[2] = -abs(nums[2])，啥意思呢，是说这个位置被人找到了，标记成负数
            // 但是，它的值只是符号变了，绝对值没变，这个绝对值还得用来标记其它的位置
            for (int i = 0; i < n; ++i) {
                int num = Math.abs(nums[i]);
                if (num <= n) {
                    nums[num - 1] = -Math.abs(nums[num - 1]);
                }
            }
            for (int i = 0; i < n; ++i) {
                if (nums[i] > 0) {
                    return i + 1;
                }
            }
            return n + 1;
        }
    }

    /**
     * 我稍微改了改 off1 的代码，更优雅了
     * 但是优雅是没什么用的，只是优雅
     * 就像普通人长得好看也没什么太大用处
     */
    static class copy_off1 {
        public int firstMissingPositive(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                if (nums[i] <= 0)
                    nums[i] = n + 1;
            }
            for (int i = 0; i < n; i++) {
                int num = Math.abs(nums[i]);
                if (num <= n && nums[num - 1] > 0) {
                    nums[num - 1] *= -1;
                }
            }
            int i;
            for (i = 0; i < n; i++) {
                if (nums[i] > 0)
                    break;
            }
            return i + 1;
        }
    }

    /**
     * 这个答案更优雅、是我原本打算的代码的样子
     */
    static class off2 {
        public int firstMissingPositive(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; ++i) {
                while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                    int temp = nums[nums[i] - 1];
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = temp;
                }
            }
            for (int i = 0; i < n; ++i) {
                if (nums[i] != i + 1) {
                    return i + 1;
                }
            }
            return n + 1;
        }
    }

    static class copy_off2 {
        public int firstMissingPositive(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                    // todo 我刚他妈发现这个交换是有顺序要求的，顺序不对会出问题
                    int t = nums[nums[i] - 1];
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = t;
                }
            }
            for (int i = 0; i < n; i++) {
                if (nums[i] != i + 1)
                    return i + 1;
            }
            return n + 1;
        }
    }
}
